package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/flip-equivalent-binary-trees/">翻转等价二叉树(Flip Equivalent Binary Trees)</a>
 * <p>我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。</p>
 * <p>只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。</p>
 * <p>这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的函数，则返回 true ，否则返回 false 。</p>
 * </p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
 *              1               1
 *            /   \           /   \
 *           2     3         3     2
 *          / \   /           \   / \
 *         4   5 6             6 4   5
 *            / \                   / \
 *           7   8                 8   7
 *      输出：true
 *      解释：我们翻转值为 1，3 以及 5 的三个节点。
 *
 * 示例 2:
 *
 *      输入: root1 = [], root2 = []
 *      输出: true
 *
 * 示例 3:
 *
 *      输入: root1 = [], root2 = [1]
 *      输出: false
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>每棵树节点数在 [0, 100] 范围内</li>
 *     <li>每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 17:10
 */
public class LC0951FlipEquivalentBinaryTrees_M {
    static class Solution {
        public boolean flipEquiv(TreeNode root1, TreeNode root2) {
            // 如果 root1 或者 root2 是 null，那么只有在他们都为 null 的情况下这两个二叉树才等价。
            if (root1  == root2) {
                return true;
            }
            // 如果 root1，root2 的值不相等，那这两个二叉树的一定不等价。
            if (root1 == null || root2 == null || root1.val != root2.val) {
                return false;
            }
            return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right))
                    || (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
        }

    }
}
